package leetcode.top100;

/**
 * 在一个由 0 和 1 组成的二维矩阵内，找到只包含 1 的最大正方形，并返回其面积。
 * <p>
 * 示例:
 * <p>
 * 输入:
 * <p>
 * 1 0 1 0 0
 * 1 0 1 1 1
 * 1 1 1 1 1
 * 1 0 0 1 0
 * <p>
 * 输出: 4
 *
 * @date 2020/4/27 23:06
 */
public class Code221_MaxSquareArea_最大正方形面积 {
    public static void main(String[] args) {
        char[][] m = {{'1', '0', '1', '0', '0'}, {'1', '0', '1', '1', '1'}, {'1', '1', '1', '1', '1'}, {'1', '0',
                '0', '1', '0'}};
        System.out.println(maximalSquare(m));

    }

    /**
     * 方式1：暴力。每次遍历i,j，寻找以该点为顶点，往下和右能够形成的最大正方形。
     *
     * 时间O((mn)²)
     */
    public int maximalSquare1(char[][] matrix) {
        int rows = matrix.length, cols = rows > 0 ? matrix[0].length : 0;
        int maxsqlen = 0;
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                //若该顶点为1，则找以该点为顶点，往下和右能够形成的最大正方形
                if (matrix[i][j] == '1') {
                    //正方形边长
                    int sqlen = 1;
                    boolean isSquare = true;
                    //如果不越界并且还是正方形，则进一步判断。扩展一行和一列
                    while (sqlen + i < rows && sqlen + j < cols && isSquare) {
                        //判断扩展的列是否都是1
                        for (int k = j; k <= sqlen + j; k++) {
                            if (matrix[i + sqlen][k] == '0') {
                                isSquare = false;
                                break;
                            }
                        }
                        //判断扩展的行是否都是1
                        for (int k = i; k <= sqlen + i; k++) {
                            if (matrix[k][j + sqlen] == '0') {
                                isSquare = false;
                                break;
                            }
                        }
                        if (isSquare)
                            sqlen++;
                    }
                    maxsqlen = Math.max(maxsqlen,sqlen);
                }
            }
        }
        return maxsqlen * maxsqlen;

    }



    /**
     * 方式2：dp
     * dp[i][j]为矩阵中“以matrix[i,j]为右下角的正方形边长”，
     * 它受限于分别以“左边、左上、右边”元素为右下角的正方形边长，取他们三个的最小值。
     *
     * 理解：以matrix[i,j]为右下角的话，相当于引入了两条边，即沿着matrix[i,j]向上，及沿着matrix[i,j]向左，
     * 现在就要看看这两条边能有多长？？
     * 这就取决于沿着这两条边之前的正方形边长能有多长。同时还得看这两条边围成的面积，是否能填满1。
     * 所以边长受三个因素制约，木桶原理，取最小值作为新正方形的边长。
     * @param matrix
     * @return
     */
    public static int maximalSquare(char[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) return 0;
        int row = matrix.length;
        int col = matrix[0].length;
        int[][] dp = new int[row][col];
        int maxLen = 0;
        for (int i = 0; i < row; i++) {
            if(matrix[i][0] == '1'){
                dp[i][0] = 1;
                maxLen = 1;
            }
        }
        for (int i = 0; i < col; i++) {
            if(matrix[0][i] == '1'){
                dp[0][i] = 1;
                maxLen = 1;
            }
        }

        for (int i = 1; i < row; i++) {
            for (int j = 1; j < col; j++) {
                if (matrix[i][j] == '1') {
                    dp[i][j] = Math.min(Math.min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1;
                    maxLen = Math.max(maxLen, dp[i][j]);
                }
                //else dp[i][j] = 0
            }
        }
        return maxLen * maxLen;

    }
}
